package lc.q51_100;

import lc.q101_150.ListNode;

import java.util.ArrayList;
import java.util.List;

public class Q89 {

    public static void main(String[] args) {

        Q89 q89 = new Q89();
        List<Integer> integers = q89.grayCode(3);
        System.out.println(integers);
    }
    public List<Integer> grayCode(int n) {
        ArrayList<Integer> integers = new ArrayList<>();
        if (n < 1) {
            return integers;
        }
        integers.add(0);
        integers.add(1);
        // 当n从2开始计算
        for (int i = 2; i <= n; i++) {
            int times = integers.size();
            // 将前面的数按顺序加上times然后拼上去就行
            List<Integer> right = new ArrayList<>();
            for (Integer integer : integers) {
                right.add(integer + times);
            }
            for (int j = times - 1; j >= 0 ; j--) {
                integers.add(right.get(j));
            }
        }
        return integers;
    }
}
